/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * 求三角形的最小路径和 
 * [ [2], 
 *  [3,4], 
 * [6,5,7], 
 *[4,1,8,3] ]
 * 最小路径为2-3-5-1 为11
 * only O(n) extra space，n is the total number of rows in the triangle.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月30日
 */
public class Triangle {
    //改进：path[i][j]=min(path[i-1][j-1],path[i-1][j])+grid[i][j]省内存的方法
    public int minimumTotal(List<List<Integer>> triangle) {
        List<Integer> path = new ArrayList<>();
        for(int i=triangle.size()-1;i>=0;i--){
            for(int j=0;j<=i;j++){
                if(i==triangle.size()-1){
                    //初始化
                    path.add(triangle.get(i).get(j));
                }else{
                    //相邻元素的和
                    path.set(j, triangle.get(i).get(j)+Math.min(path.get(j), path.get(j+1)));
                }
            }
        }
        return path.get(0);
    }
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        ArrayList<Integer> l1 = new ArrayList<Integer>();
        l1.add(-1);
        triangle.add(l1);
        
        ArrayList<Integer> l2 = new ArrayList<Integer>();
        l2.add(2);
        l2.add(3);
        triangle.add(l2);
        ArrayList<Integer> l3 = new ArrayList<Integer>();
        l3.add(1);
        l3.add(-1);
        l3.add(-3);
        triangle.add(l3);
        Triangle triangle2 = new Triangle();
        System.out.println(triangle2.minimumTotal(triangle));
    }
}
